#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>

/**
 * Luogu P1020: Missle Interception
 * This problem is a variant of LIS. DP with binary search can achieve
 * complexity of O(NlogN).
 * The solution to second question uses Dilworth's theorem:
 * In any finite partially ordered set, the largest antichain has the same size
 * as the smallest chain decomposition.
 */

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    // Input
    std::vector<int> heights;
    int h;
    while (scanf("%d", &h) != EOF) heights.push_back(h);

    // Solve as variant of LIS problem
    std::vector<int> nonIncSeq, incSeq;
    for (auto h : heights) {
        auto nonIncPos = std::upper_bound(nonIncSeq.begin(), nonIncSeq.end(), h,
                                          std::greater<int>());
        if (nonIncPos == nonIncSeq.end())
            nonIncSeq.push_back(h);
        else
            *nonIncPos = h;
        auto incPos = std::lower_bound(incSeq.begin(), incSeq.end(), h);
        if (incPos == incSeq.end())
            incSeq.push_back(h);
        else
            *incPos = h;
    }
    printf("%d\n%d\n", int(nonIncSeq.size()), int(incSeq.size()));

    return 0;
}
